package com.origin.niuke.tree;

import general_class.TreeNode;

/**
 * @author yzh
 * @version 1.0
 * @date 2022/4/19 14:31
 * 输入两棵二叉树A，B，判断B是不是A的子结构。（我们约定空树不是任意一个树的子结构）
 * 假如给定A为{8,8,7,9,2,#,#,#,#,4,7}，B为{8,9,2}，2个树的结构如下，可以看出B是A的子结构
 * 算法：递归
 * 如果两棵树当前节点的 val 相等，那么就开始判断
 * 否则，就看 root2 是否在 root1 的左边还是右边
 */
public class 树的子结构 {

    public boolean HasSubtree(TreeNode root1, TreeNode root2) {
        // 题目说空树不是任意一个树的子结构
        if (root1 == null || root2 == null) return false;
        if (root1.val == root2.val && check(root1, root2)) return true;
        return HasSubtree(root1.left, root2) || HasSubtree(root1.right, root2);
    }

    boolean check(TreeNode root1, TreeNode root2) {
        if (root1 == null) return root2 == null;
        if (root2 == null) return true;
        if (root1.val != root2.val) return false;
        return check(root1.left, root2.left) && check(root1.right, root2.right);
    }

}
